The present invention relates to vehicle navigation systems, and, more particularly, to a system for computing the optimal route from a starting point to a destination and guiding a vehicle according to the computed optimal route.
Generally, a vehicle navigation system computes the optimal route to a destination before the vehicle starts a journey. After the journey begins, the system computes local navigational guidance from the optimal route and the vehicle's present location in real time. The system gives this guidance from a starting point to a destination by presenting route information in real time on a CRT or similar display.
In cases where a vehicle has deviated from the optimal route (hereinafter called a "deviation"), a conventional navigation system generally recomputes the optimal route to the destination from a new starting point at the vehicle's present location after it has strayed. The system computes the new optimal route in the same manner as the old, in other words, to reach the destination in the shortest time or over the shortest distance. Thus the optimal route computed after a deviation may, depending on the case, require the vehicle to continue travelling in the same direction, or it may require a U-turn to retrace the original optimal route.
A vehicle deviates from an optimal route for one of two reasons: first, the driver makes a mistake; second, the driver makes a deliberate choice, for example, to avoid a traffic jam. In the latter case, should the recomputed route return the vehicle to the original route, the driver following the recomputed route as prescribed by the system may be forced into the very traffic jam he wanted to avoid. On the other hand, to avoid the traffic jam, he must deviate from the navigation system's optimal route, thereby losing the system's guidance.
Prior to the present application, the inventor of this application devised means to prevent a computation that retraces an original optimal route as a new optimal route by prohibiting a U-turn when computing the optimal route after a deviation. When a vehicle has deviated from its optimal route by mistake, however, the route that gets it to the destination in the shortest distance or the shortest time may indeed retrace the original optimal route. In that case, the preventive means causes inconvenience, because what is computed to be the optimal route under the constraint of no U-turns is not the true optimal route.